class Solution:
    def twoCitySchedCost(self, costs: list) -> int:
        costs = sorted(costs, key=lambda x: (x[0] - x[1]))
        res = 0
        start = 0
        end = len(costs) - 1
        while start < end:
            res += costs[start][0]
            res += costs[end][1]
            start += 1
            end -= 1
        return res


if __name__ == "__main__":
    print(Solution().twoCitySchedCost([[515, 563], [451, 713], [537, 709],
                                       [343, 819], [855, 779], [457, 60],
                                       [650, 359], [631, 42]]))
